package com.leetcode.根据算法进行分类.滑动窗口相关;

import com.leetcode.根据算法进行分类.中值问题相关.C_295_数据流的中位数;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author: xiaomi
 * @date: 2021/2/3
 * @description: 480. 滑动窗口中位数
 * https://leetcode-cn.com/problems/sliding-window-median/
 * TODO:快速获取中位数：使用一个大顶堆和一个小顶堆。中位数确实应该想到利用二分的思想。
 * {@link C_295_数据流的中位数}
 */
public class C_480_滑动窗口中位数 {

	public static void main(String[] args) {
		int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};

		int k = 3;
		k = 4;
		C_480_滑动窗口中位数 action = new C_480_滑动窗口中位数();
		double[] res = action.medianSlidingWindow(nums, k);
		System.out.println("res = " + Arrays.toString(res));
	}

	/**
	 * 使用新的数据结构进行优化
	 * DualHeap
	 *
	 * @param nums
	 * @param k
	 * @return
	 */
	private double[] medianSlidingWindow(int[] nums, int k) {

return null;
	}

	/**
	 * 最朴素的解法：
	 * 1.每一次移动之后再进行重新排序，重新计算中位数；
	 * 2.
	 * 我只能想到暴力解法了。
	 * 需要注意：
	 * 先将 int -> double ，就不会出现越界的问题！
	 * 还会有啥优化的方案呢？
	 * --
	 * 看了题解以后，发现居然还可以通过
	 *
	 * @param nums
	 * @param k
	 * @return
	 */
	public double[] medianSlidingWindowForce(int[] nums, int k) {
		if (nums == null) {
			return new double[0];
		}
		int len = nums.length;
		//double[] 的大小
		int size = len - k + 1;
		double[] res = new double[size];
		int midIndex = k >> 1;
		//创建一个滑动窗口的数组
		int[] arr = new int[k];
		//初始化窗口
		System.arraycopy(nums, 0, arr, 0, k);
		int begin = 0;

		if ((k & 1) == 1) {
			//如果是奇数
			for (int i = k; i < len; i++) {
				Arrays.sort(arr);
				res[begin] = arr[midIndex];
				//移除 begin 的位置的值
				for (int j = 0; j < k; j++) {
					if (arr[j] == nums[begin]) {
						arr[j] = nums[begin + k];
						break;
					}
				}
				begin++;
			}
			//处理最后一个位置，此时arr 已经完成了替换
			Arrays.sort(arr);
			res[begin] = arr[midIndex];
		} else {
			//如果是偶数
			for (int i = k; i < len; i++) {
				Arrays.sort(arr);
				res[begin] = ((double) arr[midIndex - 1] + (double) arr[midIndex]) / 2.0;
				//移除 begin 的位置的值
				for (int j = 0; j < k; j++) {
					if (arr[j] == nums[begin]) {
						arr[j] = nums[begin + k];
						break;
					}
				}
				begin++;
			}
			//处理最后一个位置，此时arr 已经完成了替换
			Arrays.sort(arr);
			res[begin] = ((double) arr[midIndex - 1] + (double) arr[midIndex]) / 2.0;
		}
		return res;
	}


	/**
	 * 如果使用数组，就是遍历O(n) + O(nlogn)
	 *
	 */
	static class DualHeap {

		/**
		 * 小顶堆
		 */
		PriorityQueue<Integer> smallTopHeap = new PriorityQueue<>();
		/**
		 * 大顶堆
		 */
		PriorityQueue<Integer> bigTopHeap = new PriorityQueue<>();

		/**
		 * 插入一个新的数
		 * @param num
		 */
		public void insert(int num){

		}

		/**
		 * 移除一个数
		 * @param num
		 */
		public void erase(int num){

		}

		/**
		 * 返回存储的数中的中位数
		 * @return
		 */
		double getMedian(){
			return 0;
		}
	}
}
